package main

import "fmt"

/*
----------希尔排序--------
前提：先理解插入排序

插入排序的优化版，分组后再插入排序
思路：             9,5,66,1,21,42
1. 按 gap = length/2 进行分组，这里 gap = 3
				9  5  66  1  21  42
	第一组：		9         1
	第二组：		   5         21
	第三组:			  66         42
2. 分别对每一组进行插入排序
3. 接着缩小步长 gap = gap/2 ,直到 gap 为0
4. 重复前面的步骤

优点：插入排序的优化版，每组排序互不影响，可以并发排序

平均时间复杂度：O(N^d) 1<d<1.5
最坏时间复杂度：O(N^2)
空间复杂度: O(1)
稳定性：不稳定
 */
func main() {
	arr := []int{9,5,66,1,21,42}
	fmt.Println(shellSort(arr))
}

/*
和插入排序的 simpleInsert 函数一样，只不过步长不一样
*/
func simpleInsert(arr []int,idx int,gap int) {
	// backup 为备份要向前插入的值，j 为前一个值
	backup,j := arr[idx],idx - gap

	for j >= 0 && arr[j] > backup{
		// 把值往后移动
		arr[j+gap] = arr[j]
		j = j - gap
	}

	// 把值放到合适的位置
	arr[j+gap] = backup
}

/*
和插入排序的 insertSort 函数一样，区别在插入排序的是整个数组，这个是插入排序一组

每一组进行插入排序
 */
func shellSortStep(arr []int, start int, gap int) {
	// 循环每一组，插入排序是循环全部数组
	for i := start + gap;i < len(arr); i += gap {
		simpleInsert(arr,i,gap)
	}
}

func shellSort(arr []int) []int{
	if len(arr) <= 1 {
		return arr
	}

	for gap := len(arr)/2;gap > 0;gap /= 2 {
		for i := 0; i < gap; i++ {
			// 对每一组进行插入排序
			shellSortStep(arr,i,gap)
		}
	}

	return arr
}
